SP9934 ALICE - Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

反之后手必胜。

问题在于石子数量可能为 11 ,这时去掉这颗石子便无法合并。

所以状态应该与石子数量为 11 的堆数,石子数量不为 11 的堆的最大操作次数有关。

SG(a,b)SG(a,b) 表示剩下 aa 堆数量为 11 的石子堆,其余石子堆能操作 bb 次的 SGSG 函数值。

那么后继状态有五种种:

  • 在石子数不为 11 的石子堆取掉一颗石子
  • 合并两堆不为 11 的石子堆
  • 取掉一堆为 11 的石子堆
  • 将两堆为 11 的石子堆合并
  • 将一堆为 11 和一堆不为 11 的石子堆合并

边界条件就是最开始讲的。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 50 , MAXV = MAXN * 1000;
int T , n;

int SG[ MAXN + 5 ][ MAXV + 5 ];
int dfs( int Cnt1 , int oper ) {
	if( SG[ Cnt1 ][ oper ] ) return SG[ Cnt1 ][ oper ];
	if( oper == 1 ) return SG[ Cnt1 ][ oper ] = dfs( Cnt1 + 1 , 0 );
	if( Cnt1 == 0 ) return SG[ Cnt1 ][ oper ] = oper % 2;
	
	int Mex = 2;
	if( Cnt1 ) Mex = min( Mex , dfs( Cnt1 - 1 , oper ) );
	if( oper ) Mex = min( Mex , dfs( Cnt1 , oper - 1 ) );
	if( Cnt1 >= 2 ) Mex = min( Mex , dfs( Cnt1 - 2 , oper + 2 + ( oper ? 1 : 0 ) ) );
	if( Cnt1 && oper ) Mex = min( Mex , dfs( Cnt1 - 1 , oper + 1 ) );
	return SG[ Cnt1 ][ oper ] = Mex == 0 ? 1 : 0;
}

int main( ) {
	scanf("%d",&T);
	for( int t = 1 ; t <= T ; t ++ ) {
		printf("Case #%d: ", t );
		
		int Cnt1 = 0 , oper = 0;
		scanf("%d",&n);
		for( int i = 1 , x ; i <= n ; i ++ ) {
			scanf("%d",&x);
			if( x == 1 ) Cnt1 ++;
			else oper += x + 1;
		}
		if( oper ) oper --; //合并次数=堆数-1
		puts( dfs( Cnt1 , oper ) ? "Alice" : "Bob" );
	}
	return 0;
}